1. Field of the Invention
This invention relates to the field of digital signal processing, and in particular to a digital filter for interpolating and decimating digitally encoded images.
2. Description of Related Art
In a digital display system, sample rate converters (SRCs) are used to effect a scaling of a digitally encoded image. A digitally encoded image, such as a video image, comprises an array of samples of the original image. A display screen area comprises an array of pixels, which may or may not correspond to the array of samples of the original image. If the number of samples in the horizontal and vertical direction are equal to the number of pixels in the horizontal and vertical direction, no scaling is necessary. Each sample is mapped to each corresponding pixel, and the resultant displayed image corresponds to the original image. If there are half the number of pixels as there are samples, every other sample is mapped to a corresponding pixel. The resultant image corresponds to an image that is sampled at half the sampling rate of the original samples. That is, a change of scale is equivalent to a change of sampling rate, hence the term xe2x80x98sample rate converterxe2x80x99. Non-integer scaling is effected by generating pixel values corresponding to an estimate of the sample value that would have been obtained had the original sampling rate corresponded to this display scale. If the image is being down-sized, or down-converted, a decimator is used to xe2x80x9cremovexe2x80x9d sample values; if the image is being up-sized, or up-converted, an interpolator is used to xe2x80x9caddxe2x80x9d sample values. Conventional display systems include both a vertical sample rate converter and a horizontal sample rate converter to effect the scaling in either or both dimensions. If the display system is configured to only provide down-scaled images, such as a xe2x80x9cpicture-in-picturexe2x80x9d feature, the sample rate converters comprise only a decimator. If the display system is configured to only present up-scaled images, such as a xe2x80x9czoomxe2x80x9d feature, the sample rate converters comprise only an interpolator. To provide both up-scaling and down-scaling, the sample rate converters of conventional high-quality display systems include both a decimator and an interpolator.
Decimators and interpolators are typically embodied as digital filters, wherein the resultant pixel value is a weighted average of the samples in the vicinity of the pixel location. The number of samples used to determine the resultant weighted average is termed the number of xe2x80x9ctapsxe2x80x9d of the digital filter. The general equation for an N-tap filter is given by:                               y          ⁡                      (                          i              +              p                        )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    c              ⁡                              (                                  n                  ,                  p                                )                                      *                                          x                ⁡                                  (                                      i                    -                    n                                    )                                            .                                                          (        1        )            
where x(i) . . . x(ixe2x88x92(Nxe2x88x921)) are the input samples at each tap of the N-tap filter, p is the phase, and c(n,p) is the weight associated with each input sample at the specified phase. To provide a variety of scale factors, a xe2x80x9cpolyphasexe2x80x9d filter is used. Each phase of a P-polyphase filter corresponds to an integer multiple of 1/P of the output scale for down-sampling, or 1/P of the input scale for up-sampling.
FIG. 1 illustrates a conceptual block diagram of an up-sampling polyphase filter with P phase stages 110a-110p. Input samples 101 are provided to each stage. If the output is an up-scaling by a factor of 1:P, the output of each stage 110a-p is selected by the switch 120, and P output values are provided in response to the receipt of each input sample 101. After producing the P output values, the next input sample 101 is received, and another P outputs are provided. In this manner, P output values are formed for each input sample, thereby providing an up-scaling by a factor of 1:P. If an up-scaling of Q:P is desired, Q of the P stages are selected for output for each input sample. For example, if Q is three, every third stage 101a, 101d, etc. is selected for output for each input sample.
FIG. 2 illustrates a conceptual block diagram of a down-sampling polyphase filter with P phase stages 210a-210p. The input samples 201 are provided to select stages via the switch 220. If the output is a downscaling by a factor of P:1, the output of all P stages 210a-p are combined by the adder 230, and a single output value 231 is provided in response to the receipt of P input samples 201. After producing the output value, another set of P inputs 201 are used to produce the next output sample 231. In this manner, one output value is formed for P input samples, thereby providing a downscaling by a factor of P:1. If a downscaling of Q:1 is desired, Q input samples 201 are provided select input stages 210a-p and the output of these stages are combined by the adder 230 to produce the single output sample 231.
A polyphase filter with N taps is typically embodied as a single filter with N registers and a memory that is configured to store the N coefficients for each of the P stages. The appropriate N coefficients are loaded into the N registers of the filter to produce each required output. U.S. Pat. No. 5,892,695, SAMPLE RATE CONVERTER, issued Apr. 6, 1999 for Age J. Van Dalfsen, Jeroen H. J. C. Stessen, and Johannes G. W. M. Janssen, discloses a polyphase filter configuration for effecting up-scaling and down-scaling, and is incorporated by reference herein. FIG. 3 illustrates an up-scaling polyphase filter as taught in the referenced patent, and FIG. 4 illustrates a down-scaling polyphase filter as also taught in the referenced patent.
In FIG. 3, each input sample x(i) 101 is sequentially clocked into the first polyphase delay elements 310. For each output sample y 121, the appropriate coefficient c(n,p(q)) is applied to the multipliers 320, where p(q) is the phase delay corresponding to the particular phase of the polyphase filter for each output sample y 121. After each of the upscaled samples y 121 are produced, the next input sample x(i) 101 is clocked into the first polyphase delay element 310, while the prior x(i) sample is clocked on to the next delay element 311, and the above process is repeated.
In FIG. 4, each input sample x(i) 201 is multiplied by the appropriate coefficient c(n,p(q)), and an intermediate sum is accumulated in the corresponding delay element 410, 411, etc. by setting the switches 440 to effect a loop of the contents of the delay element through the adder 430. When the Qth input x(i) 201 arrives in a Q:1 downscaling, the switch 440 is set to effect a transfer of the contents of each delay elements on to the next delay element, also via the adder 430 that adds the appropriate c(n,p(q))*x(i) to the accumulated sum that is transferred to the next delay element. The referenced patent contains additional detail regarding the operation of the filters of FIGS. 3 and 4.
The coefficients c(n,p) for each of the P phases of a polyphase filter are typically stored in a local memory, for application to the multipliers 320, 420 as required. The storage requirement for a P-polyphase filter with N-taps is P*N, and is illustrated by an array 510 of coefficients c(n,p) in FIG. 5. Each of the P rows of FIG. 5 contains the N-coefficients for a given phase p, each of the N columns corresponding to each of the coefficients for a given tap.
U.S. Pat. No. 4,866,647 xe2x80x9cCONTINUOUSLY VARIABLE DIGITAL DELAY CIRCUITxe2x80x9d, issued Sep. 12, 1989 to C. W. Farrow, incorporated by reference herein, describes a filter, hereinafter a xe2x80x9cFarrow filterxe2x80x9d, wherein the individual coefficient of each tap is computed based on a polynomial equation. Each column of coefficients 520 is approximated by an L-order polynomial 530 having phase p as the independent variable, and the coefficient c(n,p) 520 at this phase as the dependent variable, using conventional curve fitting techniques. By using a polynomial approximation, the coefficients c(n,p) of any phase value p can be computed, and therefore the Farrow filter provides a continuous phase filter. A continuous phase filter is conventionally termed a continuous delay filter. As contrast to the polyphase filter, which has a resolution of 1/P (interpolations beyond 1:P are limited to, at most, P unique values, any additional values being either duplicates or combinations of these P unique values), the resolution of a continuous phase filter is virtually unlimited (each phase generates a unique set of coefficients, subject only to the precision of the coefficient generator). The accuracy of the Farrow filter, compared to a polyphase filter, depends primarily upon the order of the polynomial approximation. It has been found that a third-order polynomial provides acceptable accuracy, a fourth-order polynomial being common in high quality Farrow filters. The resolution of the Farrow-filter is dependent only upon the resolution of the curve-fitting coefficients b(n,1) and the resolution of the input parameter corresponding to the phase p being estimated, hereinafter termed the delay parameter d. Preferably, the curve fitting coefficients are determined such that a range of d from 0 to 2mxe2x88x921xe2x88x921 corresponds to a range of phase from 0 to 2xcfx80, where m is the number of bits used to contain the delay term d.
FIG. 6A illustrates a block diagram of a direct embodiment of an up-scaling Farrow filter. Each of the N blocks 610, 611, . . . 615 are configured to compute the coefficients c(0), c(1), . . . c(n) for use by the filter 620 to produce the output y 121 corresponding to an input x(i) 101 and phase d 602. The filter 620 corresponds to a conventional filter, such as used in the aforementioned polyphase filter 100, as described by equation 1, repeated here for ease of reference:                               y          ⁡                      (                          i              +              p                        )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    c              ⁡                              (                                  n                  ,                  p                                )                                      *                          x              ⁡                              (                                  i                  -                  n                                )                                                                        (        1        )            
The operation of the Farrow filter can be defined as:                               y          ⁡                      (                          i              +              p                        )                          =                              ∑                          n              =              0                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    (                                                ∑                                      l                    =                    0                                    L                                ⁢                                  xe2x80x83                                ⁢                                                      b                    ⁡                                          (                                              n                        ,                        l                                            )                                                        ⁢                                      p                    l                                                              )                        ⁢                          x              ⁡                              (                                  i                  -                  n                                )                                                                        (2a)            
where b(n,1) are the coefficients of the L degree polynomial for computing each of the coefficients c(n,p) of the N taps. As can be seen, the Farrow filter requires the storage of the b(n,1) coefficients (N*(L+1) storage locations), rather than the storage of the c(n,p) coefficients (N*P storage locations). Typically, the order of the polynomial, L, is less than five (5), whereas a common polyphase filter has thirty two (32) or more discrete phases. Therefore, a Farrow filter with L-order polynomials saves (Pxe2x88x92(L+1))*N storage locations compared to a polyphase filter with P stages. Although a Farrow filter requires fewer storage locations, it requires substantially more operations per output sample, requiring at least N*(L+1)+Lxe2x88x921 multiplications for each output sample (Lxe2x88x921 multiplications to form the powers of p, plus L coefficient multiplications per tap, plus N multiplications in the filter 620), compared to a mere N multiplications per output sample in a polyphase filter.
To reduce complexity of a Farrow filter, the following transformation of terms is conventionally used:                               y          ⁡                      (                          i              +              p                        )                          =                              ∑                          l              =              0                        L                    ⁢                      xe2x80x83                    ⁢                                    (                                                ∑                                      n                    =                    0                                                        N                    -                    1                                                  ⁢                                  xe2x80x83                                ⁢                                                      b                    ⁡                                          (                                              n                        ,                        l                                            )                                                        ⁢                                      x                    ⁡                                          (                                              i                        -                        n                                            )                                                                                  )                        ⁢                          p              l                                                          (2b)            
The embodiment of equation 2b is illustrated in FIG. 6B, wherein each of the blocks 660, 661, . . . 665 are configured to generate the inner summation of equation 2b. Each of the blocks 660-665 can be embodied using the structure of FIG. 3, wherein the c(n,d) terms are replaced by the corresponding b(n,1) terms (1=0 in block 660, 1=1 in block 661, etc.). Note that the inner summation need only be computed once per input sample, each of the subsequent outputs at different phases being computed by the multipliers 630 and adders 640 as each phase p is input. This embodiment requires N*(L+1) multiplications for each input, and L multiplications for each output, a substantial reduction compared to the N*(L+1)+Lxe2x88x921 multiplications for each output of the direct embodiment of the Farrow filter. Note, however, that this optimization is limited to interpolation, wherein multiple outputs are generated for each input.
Farrow filters are not currently used in conventional video systems, due primarily to their computational complexity compared to a polyphase filter. As is known in the art, hardware multipliers are costly in terms of circuit area, and high-speed multipliers are costly in terms of power. Software filters can take advantage of general purpose high-speed multiplier co-processors, but the transfer of information for each multiplication is often too costly in time. This problem is particular acute for decimation, where the interpolation-optimized embodiment of FIG. 6B is not available.
It is an object of this invention to improve the scaling capabilities of an image display system. It is a further object of this invention to provide a selectable scaling resolution capability. It is a further object of this invention to provide a filter that can be configured to provide both decimation and interpolation capabilities.
These objects and others are provided by a variety of aspects of this invention.
In a first embodiment, a filter structure is provided that facilitates the use of the filter as either a continuous delay Farrow filter or a selectable delay polyphase filter. The less complex polyphase filter is used when the desired scale substantially corresponds to a defined phase of the polyphase filter, or when time or power is not available to achieve the desired scale exactly; otherwise, the continuous delay Farrow filter is used. By providing an ability to switch to a continuous delay, the number of stages of the polyphase filter can be reduced.
In another embodiment, an inversion of a Farrow filter is presented that provides for a continuous delay decimation filter with substantially reduced computational complexity compared to a direct embodiment of a Farrow filter. This inverted filter is also configurable as a polyphase filter, to provide selectable scale-resolution capabilities.